/*----------------------------------------------------------------
 *  Author:        Siedin Evgen
 *  Written:       9/2/2013
 *  Last updated:  10/2/2013
 *
 *  Compilation:   javac Percolation.java
 *    
 *  Percolation API
 *  Data type to model percolation system
 *
 *----------------------------------------------------------------*/

public class Percolation
{
   private int gridSize;

   private boolean[][] sites;
   
   private WeightedQuickUnionUF unionFind;
   private WeightedQuickUnionUF unionFindForFull;

   private int start;

   private int finish;

   public Percolation(int N)
   {
      sites = new boolean[N][N];
      gridSize = N;

      for (int i = 0; i < N; i++)
      {
         for (int j = 0; j < N; j++)
         {
            sites[i][j] = false;
         }
      }

      unionFind = new WeightedQuickUnionUF(N * N + 2);
      unionFindForFull = new WeightedQuickUnionUF(N * N + 1);

      start = N * N;
      finish = N * N + 1;
   }

   public boolean percolates()
   {
      return unionFind.connected(start, finish);
   }

   public void open(int i, int j)
   {
      checkGridIndex(i, j);

      if (!isOpen(i, j))
      {
         sites[i - 1][j - 1] = true;
         connectToOpenNeighbours(i, j);
      }
   }

   public boolean isOpen(int i, int j)
   {
      checkGridIndex(i, j);

      return sites[i - 1][j - 1];
   }

   public boolean isFull(int i, int j)
   {
      checkGridIndex(i, j);

      if (isOpen(i, j))
      {
         return unionFindForFull.connected(translateCoord(i, j), start);
      }
      
      return false;
   }
   
   private void union(int i, int j)
   {
       unionFind.union(i, j);
       unionFindForFull.union(i, j);
   }        

   private void connectToOpenNeighbours(int i, int j)
   {
      if (j != 1 && isOpen(i, j - 1))
         union(translateCoord(i, j), translateCoord(i, j - 1));
      if (j != gridSize && isOpen(i, j + 1))
         union(translateCoord(i, j), translateCoord(i, j + 1));
      if (i != 1 && isOpen(i - 1, j))
         union(translateCoord(i, j), translateCoord(i - 1, j));
      if (i != gridSize && isOpen(i + 1, j))
         union(translateCoord(i, j), translateCoord(i + 1, j));

      if (i == 1) union(translateCoord(i, j), start);

      if (i == gridSize) unionFind.union(translateCoord(i, j), finish);
   }

   private int translateCoord(int i, int j)
   {
      return (i - 1) * gridSize + j - 1;
   }

   private void checkGridIndex(int i, int j)
   {
      if (i < 1 || i > gridSize || j < 1 || j > gridSize)
      {
         throw new IndexOutOfBoundsException();
      }
   }
}
